The present invention relates to a voice coder using PSMQ (predictive split matrix quantization) and PSVQ (predictive split vector quantization) of LSP (line spectrum pair) coefficient. In particular, the present invention relates to a fast search method for LSP quantization in PSMQ or PSVQ.
Generally, voice-coding methods with analysis-by-synthesis structure extract parameters that represent voice signal and quantize the parameters for transmission. The voice-coding methods reduce the amount of data to be transmitted in environments of limited bandwidth.
In order to perform high quality voice coding, low speed voice coders should quantize LPC (linear predictive coding) coefficients efficiently. LPC coefficients describe the relativity of voice signals in short range. Optimal LPC coefficients are obtained in the following way. First, the input voice signal is divided into frame units. Then, LPC coefficients are obtained as the energy of expectation error is minimized in each frame. Generally, LPC filters are to the 10th order, all-pole filters and a number of bits are allocated to quantize the 10 LPC coefficients. For example, in the case of IS-96A QCELP, which is a voice coding method in CDMA mobile communication systems, 25% of the total bits are used for LPC quantization.
So far, a number of methods have been proposed for LPC coefficient quantization, and they are practically used for voice coders. The methods, in which LPC coefficients are directly quantized, are too sensitive for quantization error of coefficients and there is no guarantee that LPC filters are stable after quantization.
Therefore, LPC coefficients should be converted into different parameters having good quantization characteristics, and usually they are converted into reflection coefficients or LSP (line spectrum pairs). Especially, since LSP is closely related with frequency characteristics of voice signals, recently developed standard voice coders mostly employ LSP quantization methods.
In addition, more efficient quantization is possible by using correlation of LSP between frames. That is, the LSP of the current frame is not directly quantized. Instead, the LSP of the current frame is expected on the basis of LSP information regarding previous frames and the difference of the LSP expected between the two frames is quantized. The LSP value may be expected in terms of time because it is heavily related with frequency characteristics of voice signals and it results in a relatively high expectation gain.
Here, the two LSP expectation methods are explained. One is using an AR (auto-regressive) filter and the other method uses an MA (moving average) filter. AR filters are superior to MA filters in expectation capability yet it is problematic because the effect of the coefficient error propagates through frames. On the contrary, though expectation capability of MA filters is not as good as one of the AR filters, MA filters are advantageous in that the effect of a coefficient error is restricted in terms of time. Consequently, voice coders used in a wireless communication environment like AMR, CS-ACELP, and EVRC usually employ MA filters for LSP expectation.
In addition, other than expecting LSP value between frames, a quantization method using correlation between adjacent LSP components is developed. Since LSP always satisfies an ordering property, this quantization method improves quantization efficiency.
There are vector quantization and scalar quantizations in quantizing the expected LSP coefficients. An 8 kbps QCELP voice coder uses scalar quantization. Since an 8 kbps QCELP voice coder scalar-quantizes each LSP component, relatively, many bits are allocated (40 bit) in comparison with voice coders with almost the same performance. Recently, the vector quantization method is employed for efficient quantization and many studies have been performed in the area.
In vector quantization, to quantize all vectors at once is impossible because the vector table is going to be too big and the time for a search is going to be enormous. To solve the problem, one large vector is split into several small vectors before quantization, and this method is called SVQ (split vector quantization). For example, in a 10th order vector quantization using 20 bits quantizing the vector once requires a 10xc3x971020 vector table. If the vector is split into two fifth-order vectors and 10 bits are allocated for a vector, the size of the vector table is 5xc3x971010xc3x972.
The vector may be split into more small vectors for a smaller vector table size and it results in a small amount of memory and faster searching. However, correlation between vector values is not fully utilized in such cases and, therefore, performance is deteriorated. In the extreme, if a 10th order vector is split into ten first order vectors, it becomes scalar quantization.
If SVQ is used and the LSP is directly quantized without expecting the LSP between 20 ms frames, a quantization performance of 24 bits may be obtained. However, since SVQ quantizes sub-vectors independently, correlation between the sub-vectors is not fully utilized, and therefore, optimization of the total vector is not accomplished.
Other than SVQ, there are several quantization methods such as multi-stage quantization, selective vector quantization, and linked split vector quantization. Multi-stage quantization divides quantization process into several stages. Selective vector quantization employs two tables and performs selective quantization. Linked split vector quantization reviews boundary values between sub-vectors and selects appropriate vector quantization tables.
A fast search method for LSP (Linear Spectrum Pair) quantization is provided. The fast search method in accordance with an embodiment of the present invention includes the following steps. A first step is obtaining a target vector and a code vector. The target vector and the code vector are converted for ordering property. A second step is generating a code book having the ordering property for sub-matrices by utilizing the target vector and the code vector. A third step is selecting a particular line for determining a search scope in the code books and sorting the code book in descending order with respect to component values of the particular line. A fourth step is determining the search scope by utilizing the ordering property of the target vector and the sorted code vectors. The fifth step is obtaining an error standard by utilizing the target vector and the code vector, and obtaining an optimal code vector by utilizing the error standard within the determined search scope.
Preferably, the first step includes following sub-steps. The first sub-step is obtaining a target vector for the mth sub-matrix, with an ordering property, by utilizing the LSP vector average value of the mth sub-matrix and the expectation value of the mth sub-matrix. The second sub-step is obtaining the lth code vector of the mth sub-matrix by utilizing the lth error code book of the mth sub-matrix and the lth DC component of the mth sub-matrix. The lth DC component of the mth sub-matrix has an ordering property. The third sub-step is obtaining an error standard by utilizing the target vector of the mth sub-matrix and the lth code vector of the mth sub-matrix and determining the code book index that minimizes the error standard.
Preferably, the error standard is obtained by applying the target vector of the mth sub-matrix and the lth code vector of the mth sub-matrix to the following equation 1 and equation 2.                                                                         E                                  m                  ,                  l                                            =                                                ∑                                      i                    =                    0                                    3                                ⁢                                  xe2x80x83                                ⁢                                                      [                                                                  (                                                                              r                                                          m                              ,                              i                                                                                +                                                      L                                                          DC                              ,                              m                              ,                              i                                                                                -                                                      r                                                          m                              ,                              l                              ,                              i                                                        xe2x80x2                                                    -                                                      L                                                          DC                              ,                              m                              ,                              i                                                                                                      )                                            ⁢                                              w                                                  m                          ,                          i                                                                                      ]                                    2                                                                                                        =                                                ∑                                      i                    =                    0                                    3                                ⁢                                                      [                                                                  {                                                                              (                                                                                          L                                                                  m                                  ,                                  i                                                                                            -                                                              p                                                                  m                                  ,                                  i                                                                                                                      )                                                    -                                                      (                                                                                          r                                                                  m                                  ,                                  l                                  ,                                  i                                                                xe2x80x2                                                            +                                                              L                                                                  DC                                  ,                                  m                                  ,                                  i                                                                                                                      )                                                                          }                                            ⁢                                              w                                                  m                          ,                          i                                                                                      ]                                    2                                                                                                        =                                                ∑                                      i                    =                    0                                    3                                ⁢                                                      [                                                                  (                                                                              R                                                          m                              ,                              i                                                                                -                                                      C                                                          m                              ,                              l                              ,                              i                                                                                                      )                                            ⁢                                              w                                                  m                          ,                          i                                                                                      ]                                    2                                                                                                        =                              min                ⁡                                  (                                                            E                                              m                        ,                        l                                                              ,                                          E                                              m                        ,                        l                                                                    (                        +                        )                                                                              )                                                                                        [                  Equation          ⁢                      xe2x80x83                    ⁢          1                ]                                                                                    E                                  m                  ,                  l                                                  (                  +                  )                                            =                              xe2x80x83                            ⁢                                                ∑                                      i                    =                    0                                    3                                ⁢                                                      [                                                                  (                                                                              R                                                          m                              ,                              i                                                                                -                                                      C                                                          m                              ,                              l                              ,                              i                                                                                -                                                      2                            ⁢                                                          L                              DC                                                                                                      )                                            ⁢                                              w                                                  m                          ,                          i                                                                                      ]                                    2                                                                                                                                          R                                      m                    ,                    i                                                  =                                  xe2x80x83                                ⁢                                                      L                                          m                      ,                      i                                                        -                                      P                                          m                      ,                      i                                                                                  ,                                                                                          C                                  m                  ,                  l                  ,                  i                                            =                              xe2x80x83                            ⁢                                                r                                      m                    ,                    l                    ,                    i                                    xe2x80x2                                +                                  L                                      DC                    ⁢                                          ,                                              m                        ,                        i                                                                                                                                                    [                  Equation          ⁢                      xe2x80x83                    ⁢          2                ]            
Preferably, the DC component is the LSP vector average value.
Preferably, the third step includes following sub-steps. The first sub-step is selecting a fourth line for the first code book, a third line for the second code book, the third code book, and the fourth code book, and fourth line for the fifth code book as a particular line. The second sub-step is sorting the whole code book in descending order with respect to the selected particular line.
Preferably, the fourth step obtains a starting point of the search scope by forward direction comparison and an ending point of the search scope by reverse direction comparison. The forward direction comparison compares the nth line component of the sorted code book with the (n+1)th line component of target vector. The reverse direction comparison compares the nth line component of the sorted code book with the (nxe2x88x921)th line component of target vector.
Preferably, the process of obtaining the starting point obtains the smallest l value satisfying Rn+1 greater than Cl,n, Rn+1 being n+lth target vector for the code book search of sub-matrix. Cl,n is the nth code vector of the lth sub-matrix.
Preferably, the process of obtaining the starting point includes the following sub-steps. The first sub-step is finding i, satisfying Rn+1 greater than Ci+64,n, by increasing i by 64. The second sub-step is for setting the variable j=i and finding j, satisfying Rn+1 greater than Cj+16,n, by increasing j by 16. The third sub-step is setting variable k=j and finding k, satisfying Rn+1 greater than Ck+4,n, by increasing k by 4. The fourth sub-step is setting variable m=k and finding m+1, satisfying Rn+1 greater than Cm+1,n, by increasing m by 1. The fifth sub-step is setting the m+1 as the starting point.
Preferably, the process of obtaining the ending point obtains the smallest l value satisfying Rnxe2x88x921 less than Cl,n. Rnxe2x88x921 is the nxe2x88x92lth target vector for the code book search of sub-matrix. Cl,n is the nth code vector of the lth sub-matrix.
Preferably, the process of obtaining the ending point includes the following sub-steps. The first sub-step is setting an initial value of i based upon the index number of each code book. The second sub-step is finding i, satisfying Rnxe2x88x921 greater than Cixe2x88x9264,n, by decreasing i by 64. The third sub-step is setting variable j=i and finding j, satisfying Rnxe2x88x921 greater than Cjxe2x88x9216,n, by decreasing j by 16. The fourth sub-step is setting variable k=j and finding k, satisfying Rnxe2x88x921 greater than Ckxe2x88x924,n, by decreasing k by 4. The fifth sub-step is setting variable m=k and finding m, satisfying Rnxe2x88x921 greater than Cmxe2x88x921,n, by decreasing m by 1. The sixth sub-step is setting the m+1 as ending point l.
Preferably, the initial value of i is set 128 for setting the ending point of the first code book search, 256 for setting the ending point of the second, third, and fourth code book search and then to 64 for setting the ending point of the fifth code book search.
Preferably, the fourth step includes following sub-steps. The first sub-step is sorting the third code book in ascending order by subtracting DC component from the third code book, multiplying a result of the subtraction by xe2x88x921, and adding the DC component, if a sign bit of third code book is 1. The third code book is sorted in descending order by the ordering property. The second sub-step is obtaining a starting point of the search scope by reverse comparison. The reverse comparison compares the nth line component of the sorted third code book with the (nxe2x88x921)th line component of target vector. The third sub-step is obtaining an ending point of the search scope by a forward comparison. The forward comparison compares the nth line component of the sorted third code book with the (n+1)th line component of target vector.
Preferably, the process of obtaining the starting point obtains the smallest l value satisfying Rn+1 greater than Cl,n, with Rn+1 being the n+1th target vector for a code book search of sub-matrix, and Cl,n being the nth code vector of lth sub-matrix.
Preferably, the initial value of i is set at 128 for setting the starting point of the first code book search, 256 for setting the starting point of the second code book search, third code book search, and fourth code book search, and at 64 for setting the starting point of the fifth code book search.
A fast search method implemented in a computer system for LSP (Linear Spectrum Pair) quantization is provided. The fast search method for LSP (Linear Spectrum Pair) quantization in accordance with an embodiment of the present invention, includes following steps. The first step is obtaining a target vector and a code vector, the target vector and the code vector are converted for ordering property. The second step is generating a code book having the ordering property for sub-matrices by utilizing the target vector and the code vector. The third step is selecting a particular line for determining a search scope in the code book and sorting the code book in a regular order with respect to component values of the particular line. The fourth step is determining the search scope by utilizing the ordering property of the target vector and the sorted code vectors. And the fifth step is obtaining an error stand by utilizing the target vector and the code vector, and obtaining an optimal code vector by utilizing the error standard within the determined search scope.
Preferably, the LSP quantization is implemented by a predictive split VQ (Vector Quantization) method or a predictive split MQ (Matrix Quantization) method.